"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""

class Solution:

    def has_cycle(self, node):
        slow, fast = node, node

        slow_dis = 0
        while fast and fast.next:       # 如果fast为null, 则不会再执行and之后的fast.next
            slow_dis += 1
            slow = slow.next
            fast = fast.next.next       # 可能取None/Swallow

            if slow is fast:
                # slow.show_v()
                print('slow_dis is [%s]' % slow_dis)
                return slow

        return None


    """
    @param head: The first node of linked list.
    @return: The node where the cycle begins. if there is no cycle, return null
    """
    def detectCycle(self, node):
        meet_node = self.has_cycle(node)
        if not meet_node:
            return None

        n1 = node
        n2 = meet_node
        dis = 0
        while n1 != n2:
            dis += 0
            n1, n2 = n1.next, n2.next

        return n1
